동기화 문제
프로세스 동기화란?
프로세스 동기화(Process Synchronization)란, 프로세스끼리 통신을 하는 경우에 누가 먼저 작업할지, 작업이 언제 끝날지 등을 서로 알려주어야 하는데 이것들을 알려주면서 자원의 일관성을 지키는 것을 프로세스 동기화라고 한다.
프로세스 간 통신의 종류와 분류
이러한 동기화 문제는 프로세스 간의 통신에서 발생하는데 프로세스 간 통신의 종류는 다음과 같다.
- 프로세스 내부 데이터 통신 : 1개의 프로세스 안에 2개 이상의 스레드가 존재하는 경우
- 프로세스 간 데이터 통신 : 같은 컴퓨터 내에서 여러개의 프로세스끼리 통신하는 경우
- 네트워크를 이용한 데이터 통신 : 여러 컴퓨터가 네트워크를 이용해서 통신하는 경우
위와 같은 프로세스간의 통신은 통신 방향, 통신 구현 방식에 따라 분류 할 수 있는데 이는 다음과 같다.
통신 방향에 따른 분류
- 양방향 통신 ex) 일반적 통신, 소켓
- 반양방향 통신 ex) 무전기
- 단방향 통신 ex) 전역 변수, 파이프
통신 구현 방식에 따른 분류
- 대기가 있는 통신 ex) 파이프, 소켓
- 대기가 없는 통신 ex) 전역 변수, 파일
마지막으로, 프로세스 간의 통신을 하는 방법은 크게 4가지가 있는데 아래와 같다.
- 전역 변수를 이용한 통신
- 파일을 이용한 통신
- 파이프를 이용한 통신
- 소켓을 이용한 통신
이와 같은 프로세스 간의 통신은 데이터의 동기화가 상당히 중요한데 이제 본격적으로 이 동기화 문제에 대해 다뤄 보도록 하자.
공유자원과 임계구역
공유 자원은 여러 프로세스가 공동으로 이용하는 변수, 메모리, 파일 등을 말한다.
공유자원은 공동으로 이용되기 때문에 누가 언제 데이터를 읽거나 쓰느냐에 따라 그 결과가 달라질 수 있다.
이같이, 2개 이상의 프로세스가 공유 자원을 병행적으로 읽거나 쓰는 상황을 경쟁 조건(race condition)이 발생했다고 한다.
경쟁 조건이 발생하면 공유 자원 접근 순서에 따라 실행 결과가 달라질 수 있는데, 이 실행 결과가 달라질 수 있는 프로그램의 영역을 임계구역(critical section)이라고 한다.
임계구역의 문제 : 생산자-소비자 문제
임계구역에 관련된 문제로 생산자-소비자 문제(producer-consumer problem)가 있다. 한정 버퍼 문제(bounded-buffer problem)라고도 한다.
생산자 프로세스와 소비자 프로세스가 서로 독립적으로 작업을 한다.
유한한 개수의 물건(데이터)을 임시로 보관하는 보관함(버퍼)에 여러 명의 생산자들과 소비자들이 접근한다. 생산자는 물건이 하나 만들어지면 그 공간에 저장한다. 이때 저장할 공간이 없는 문제가 발생할 수 있다. 소비자는 물건이 필요할 때 보관함에서 물건을 하나 가져온다. 이 때는 소비할 물건이 없는 문제가 발생할 수 있다.
위와 같은 생산자 소비자 문제는 소프트웨어적인 문제에서 발생하지만 임계구역의 문제는 하드웨어 문제 또한 존재한다. 프린터를 모두가 써야하는 상황에 동시에 출력이 된다면 그림이 겹쳐서 프린트될 것이다. 이러한 문제 때문에 하드웨어도 한번에 한 프로세스만 사용해야 한다.
임계구역 해결 조건
임계구역을 해결하는 조건에는 크게 상호 배제, 한정 대기, 진행의 융통성 3가지가 있다. 어떤 것들인지 코드와 함께 해결 방법과 같이 자세하게 알아보도록 하자.
상호 배제
상호 배제(mutual exclusion)이란, 한 프로세스가 임계구역에 들어가면 다른 프로세스는 임계구역에 들어갈 수 없다는 뜻이다. 이것이 지켜지지 않으면 임계구역을 설정한 의미가 없고, 임계구역 내에는 한번에 하나의 프로세스만 있어야 한다.
아래의 코드로 이제 어떻게 상호 배제가 일어날 수 있는지 살펴보자.
#include <stdio.h>
typedef enum {false, true} boolean;
extern boolean lock = false;
extern int balance;
main() {
while(lock==true);
lock = true;
balance = balance+10; // 임계 구역
lock = false;
}
프로세스1은 while(lock==true);문을 실행한다. 임계구역에 프로세스가 없기 때문에 이 무한루프를 빠져나오게 되고, 다음 문장을 실행하려는 순간 주어진 cpu타임을 다써서 준비 상태로 옮겨진다. 이 때 문맥 교환이 발생하여 프로세스 p2가 실행 상태로 바뀐다.
위의 코드는 프로세스1이 lock=true;로 진입해야만 정상적으로 프로세스2가 임계구역으로 진입을 할 수 없을 것이다. 하지만 cpu시간이 끝남에 따라 임계구역에 두개의 프로세스가 들어오게 되어 상호 배제의 조건을 만족하지 못하게 된다.
또한, 계속 프로세스가 while문을 도는 과정에서 시스템 자원을 낭비하고 있다고 볼 수도 있다.
한정 대기
한정 대기(bounded waiting)이란, 어떤 프로세스도 무한 대기를 해서는 안된다는 것이다. 즉, 특정 프로세스가 임계구역에 진입하지 못하면 안 된다.
#include <stdio.h>
typedef enum {false, true} boolean;
extern boolean lock1 = false;
extern boolean lock2 = false;
extern int balance;
// 메인 수도 코드
main() {
lock1 or lock2 = true;
while(lock1 or lock2==true);
balance = balance+10; // 임계 구역
lock1 or lock2 = false;
}
잠금을 2개 사용하여 상호 배제를 보장하는 코드를 만들었다. 프로세스1은 임계구역에 진입하기 전에 lock1을 true로 설정하고 프로세스2는 lock2를 true로 설정한다고 가정해보자. 위의 코드는 상호배제 조건은 만족하지만, 한정 대기 문제를 해결하지 못하였다.
- 프로세스1은 lock1=true; 문을 실행한 후 자신의 cpu시간을 다써버렸다. 문맥 교환이 발생하고 p2가 실행 상태로 바뀐다.
- 프로세스2는 lock2=true문을 실행한 후 자신의 cpu시간을 다써버렸다. 문맥 교환이 발생하고 p1이 실행 상태로 바뀐다.
이러한 상황에서 프로세스1과 프로세스2가 둘다 계속 무한루프에 빠지는 상황이 발생할 수 있다. 이러한 상황을 교착 상태(deadlock)이라고도 한다.
또한 위의 코드는 프로세스 개수마다 lock의 개수가 추가되므로 비효율적인 코드라고 볼 수 있다.
진행의 융통성
진행의 융통성(progress flexibility)란, 한 프로세스가 다른 프로세스의 진행을 방해해서는 안 된다는 것을 의미한다.
#include <stdio.h>
typedef enum {false, true} boolean;
extern int lock = 1;
extern int balance;
// 프로세스 1 메인 수도 코드
main() {
while(lock == 2);
balance = balance+10; // 임계 구역
lock = 2;
}
위의 코드는 lock 값이 1이면 프로세스1이 임계구역을 사용한다는 뜻이고, lock값이 2이면 프로세스2가 임계구역을 사용한다는 뜻이다.
위의 코드는 상호배제와 한정 대기 조건을 충족했지만 진행의 융통성을 충족하지 못한다.
위의 코드는 서로 번갈아 가면서 실행된다는 것이 문제인 코드이다. 한 프로세스가 두 번 연달아 임계구역에 진입하고 싶어도 그럴 수가 없다. 위의 코드 처럼 프로세스의 진행이 다른 프로세스로 인해 방해받는 현상을 경직된 동기화(lockstep synchronization)이라고 한다.
임계 구역 해결 방법
임계 구역 해결 방법에는 크게 하드웨어적인 방법과 소프트웨어적인 알고리즘 방법이 존재한다. 이 방법들에 대해서 살펴보자.
하드웨어 적인 해결 방법
앞서 살펴본 조건들의 코드에서는 while(lock == true); 문과 lock=true문이 분리되어 실행되어 타임아웃이 걸리면 문제가 발생하였는데, 하드웨어적으로 두 명령어를 동시에 실행하면 임계구역 문제를 쉽게 해결할 수 있다. 하지만 하드웨어적인 방법이 편리하긴 하지만, 바쁜 대기를 사용하여 검사하기 때문에 자원 낭비가 있다. 일부 하드웨어는 바쁜 대기 없이 잠금을 동기화하지만 이는 성능 좋은 하드웨어에서나 가능한 일이다.
그렇다면 이를 해결한 소프트웨어적인 두가지의 알고리즘을 살펴보자.
피터슨 알고리즘
피터슨 알고리즘은 임계구역 문제를 해결하기 위해 게리 피터슨이 제안한 것이다.
turn이라는 공유 변수를 추가적으로 사용한다는 특징이 있다.
#include <stdio.h>
typedef enum {false, true} boolean;
extern int lock = 1;
extern int balance;
extern int turn = 1;
// 프로세스 1 메인 수도 코드
main() {
lock1 = true;
turn = 2;
while(lock2 == true && turn == 2);
balance = balance+10; // 임계 구역
lock1 = false;
}
여기서 변수 turn은 두 프로세스가 동시에 lock을 설정하여 임계구역에 못 들어가는 상황에 대비하기 위한 것이다. 즉, 두 프로세스가 동시에 lock을 설정했더라도 turn을 사용하여 다른 프로세스에게 양보한다.
하지만 피터슨 알고리즘은 임계구역 해결의 세가지 조건을 모두 만족하지만 2개의 프로세스에서만 사용 가능하다는 한계가 있다.
데커 알고리즘
데커 알고리즘은 테오도리스 데커가 제안한 알고리즘으로 이또한 임계구역 해결의 세가지 조건을 모두 만족한다.
#include <stdio.h>
typedef enum {false, true} boolean;
extern int lock = 1;
extern int balance;
extern int turn = 1;
// 프로세스 1 메인 수도 코드
main() {
lock1 = true;
while(lock2==true){
if(turn==2){
lock1=false;
while(turn==2);
lock1=true;
}
}
balance = balance+10; // 임계 구역
turn=2;
lock1=false;
}
이코드의 흐름은 다음과 같다.
- 프로세스1은 잠금을 건다 (lock1 = true)
- 프로세스2의 잠금이 걸렸는지 확인한다 (while(lock2==true))
- 프로세스2가 잠금을 걸었다면 누가 먼저인지 확인한다. 만약 프로세스1의 차례라면 임계구역으로 진입한다.
- 만약 프로세스2의 차례라면 프로세스1은 잠금을 풀고 프로세스2가 작업을 마칠때까지 기다린다. 프로세스2가 작업을 마치면 잠금을 걸고 임계구역으로 진입한다.
데커 알고리즘은 알고리즘이 복잡할 뿐만 아니라 프로세스가 늘어나면 변수도 늘어나고 전체적인 알고리즘도 복잡해진다는 단점이 있다.
세마포어(Semaphore)
세마포어는 앞의 알고리즘과 비교하면 간단하고 사용하기 쉽다.
세마포어는 임계구역에 진입하기 전에 스위치를 사용 중으로 놓고 임계구역으로 들어간다. 이후에 도착하는 프로세스는 앞의 프로세스가 작업을 마칠 때 까지 기다린다. 프로세스가 작업을 마치면 세마포어는 다음 프로세스에 임계구역을 사용하라는 동기화 신호를 보낸다. 세마포어는 다른 알고리즘과 달리 임계구역이 잠겼는지 직접 점검하거나, 바쁜 대기를 하거나, 다른 프로세스에 동기화 메시지를 보낼 필요가 없다.
tip
바쁜 대기 : 바쁜 대기(영어: busy waiting 또는 spinning)란 어떠한 특정 공유자원에 대하여 두 개 이상의 프로세스나 스레드가 그 이용 권한을 획득하고자 하는 동기화 상황에서 그 권한 획득을 위한 과정에서 일어나는 현상이다. 프로그래밍 적으로 설명하자면 기다리는 쓰레드가 공유 자원을 사용할수 있는지 없는지 계속해서 무한 루프를 돌면서 조건문을 체크하는 방식이 바쁜 대기이다. 이 바쁜대기라고 불리는 busy waiting은 cpu의 자원을 쓸데없이 낭비하기 때문에 좋지 않은 쓰레드 동기화 방식이다.
Semaphore(n);
P();
임계구역코드()
V();
- Semaphore(n): 현재 사용 가능한 자원 수가 담겨있는 전역변수 RS를 n으로 초기화 한다.
- P() : 잠금을 수행하는 코드로, RS가 0보다 크면 1만큼 감소시키고 임계구역에 진입한다. 만약 RS가 0보다 작으면 0보다 커질때까지 기다린다.
- V() : 잠금해제와 동기화를 같이 수행하는 코드로, RS 값을 1 증가시키고 세마포어에서 기다리는 프로세스에게 임계구역에 진입해도 좋다는 wake_up 신호를 보낸다.
프로세스1과 프로세스2가 세마포어로 어떻게 서로 동기화를 해결하는지 과정을 살펴보자. (RS의 초깃값은 1이라고 가정)
- 먼저 도착한 프로세스1이 임계구역에 진입한다. 현재 RS는 1이므로 이 값을 1감소 시키고 임계구역에 진입한다.
- 나중에 도착한 프로세스2는 현재 RS값이 0이므로 p1이 임계구역을 빠져나올때 까지 세마포어 큐에서 기다린다.
- 프로세스1은 작업을 마치고 RS값을 1증가시키고 wake_up 신호를 프로세스2에게 보낸다.
- wake_up 신호를 받은 프로세스2가 작업을 시작한다.
위와 같은 세마포어는 공유 자원이 여러개일 때도 사용할 수 있다는 장점이 있다.
뮤텍스(Mutal Exclusion)
뮤텍스는 상호 배제라고도 하는데, 0또는 1의 값을 가지는 이진 세마포어와 유사하다는 특징이 있다.
뮤텍스는 일종의 locking 메커니즘으로 lock을 가지고 있을 때만 임계영역에 접근이 가능하다.
앞서 설명한 데커 알고리즘과 피터슨 알고리즘이 이 뮤텍스 기법중 하나이기도 하다.
모니터
모니터는 시스템 호출과 같은 개념이다. 커피머신을 사용자가 직접 만지면 고장 날 가능성이 있는 것처럼, 운영체제가 관리하는 자원을 사용자가 마음대로 사용하게 두면 실수나 악의적인 의도로 시스템 자원을 망가뜨릴 수 있다. 이러한 문제를 예방하기 위해 운영체제는 시스템 자원을 사용자로부터 숨기고 사용자의 요구사항을 처리할 수 있는 인터페이스만 제공하는데, 이를 시스템 호출이라고 한다.
모니터의 작동 원리는 다음과 같다.
- 임계구역으로 지정된 변수나 자원에 접근하고자 하는 프로세스는 직접 P()나 V()를 사용하지 않고 모니터에 작업 요청을 한다.
- 모니터는 요청받은 작업을 모니터 큐에 저장한 후 순서대로 처리하고 그 결과만 해당 프로세스에 알려준다.
이러한 작동원리는 public과 private를 사용하는 자바같은 객체지향 언어와 많이 닮은 점이 있다.
세마포어 vs 뮤텍스 vs 모니터
뮤텍스와 모니터의 차이는?
- 뮤텍스는 다른 프로세스나 스레드 간에 동기화를 위해 사용한다.
- 모니터는 하나의 프로세스내에서 다른 스레드 간에 동기화할 때 사용한다.
- 뮤텍스는 운영체제 커널에 의해 제공된다.
- 모니터는 프레임워크나 라이브러리 그 자체에서 제공된다.
세마포어와 모니터의 차이는?
- 자바에서는 모니터를 모든 객체에게 기본적으로 제공하지만 C에서는 사용할 수 없음.
- 세마포어는 카운터라는 변수값으로 프로그래머가 상호 배제나 정렬의 목적으로 사용시 매번 값을 따로 지정해줘야 하는 등 조금 번거롭다.
- 반면, 모니터는 이러한 일들이 캡슐화되어 있어서 개발자는 카운터 값을 0 또는 1으로 주어야 하는 고민을 할 필요가 없이 synchronized, wait(), notify() 등의 - 키워드를 이용해 좀 더 편하게 동기화할 수 있다.
세마포어와 뮤텍스의 차이는?
- 세마포어는 뮤텍스가 될 수 있지만, 뮤텍스는 세마포어가 될 수 없다.
- 세마포어는 소유할 수 없으며, 뮤텍스는 소유할 수 있고 소유주가 그 책임을 진다.
- 뮤텍스의 경우 뮤텍스를 소유하고 있는 스레드가 이 뮤텍스를 해제할 수 있다. 하지만 세마포어는 소유하지 않고 있는 다른 스레드가 세마포어를 해제할 수 있다.
- 뮤텍스는 동기화 대상이 1개일 때 사용하고 세마포어는 동기화 대상이 여러 개일때 사용한다.
마지막으로, 세마포어와 뮤텍스를 비교하는데 항상 나오는 화장실 문제이다. 링크를 가서 꼭 읽어보는 것을 추천한다.
나올 수 있는 면접 질문
- 프로세스 동기화란 무엇인가요?
- 동기화 문제에서 임계구역 문제를 해결하기 위한 세가지 조건은 어떤 것들이 있나요?
- 간단한 코드로 임계구역 문제를 설명해주세요.
- 임계구역 문제를 해결하기 위한 알고리즘을 알고 계신가요?
- 세마포어, 뮤텍스, 모니터는 무엇일까요?
참고 url
기여자
Kyun Heo
📦